package arithmetic.LeetCode;

import org.junit.jupiter.api.Test;

/**
 * @author jiangfeng on 2022/6/6
 */
public class FindMinRotated {

    @Test
    public void test(){
        //findMin(new int[]{3,4,5,1,2});
        System.out.println(findMin(new int[]{3,1,2}));
    }

    public int findMin(int[] nums) {
        int l = 0,r = nums.length-1;
        while(l<r){
            int mid = l+(r-l)>>1;
            if(nums[mid]>= nums[l]){
                if(nums[mid]>nums[r]){
                    l = mid +1;
                }else{
                    r=l;
                }
            }else{
                r = mid;
            }
        }
        // l ==r
        return nums[l];


    }


    @Test
    public void test2(){
        System.out.println(findPeakElement(new int[]{1,2,3,1}));
    }

    // 关键点:
    //1. 可以类比找最大值,  峰值一定会发生在值叫大的一方.
    //2.由于mid的计算会丢失精度,中间点会偏向左边一点(如l和r相差1时,中间值就是l),所以 一定让l承担收敛值的角色,并且l值每次


    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }


    public int findPeakElement2(int[] nums) {
        int l = 0,r = nums.length-1;
        while(l<r){
            int mid = l + ((r-l)>>1);

            if(nums[mid] >  nums[mid+1]){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
}
